/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

/**
 * @author zhong
 *
 */
public class SpecialBinaryString {
	public String makeLargestSpecial(String S) {
		return makeLargestSpecial(S, new int[] { 0 });
	}

	public String makeLargestSpecial(String S, int i[]) {
		StringBuilder reStringBuilder = new StringBuilder();
		ArrayList<String> list = new ArrayList<>();
		// 现在i指着开始的1--一定，但是不一定
		int start = i[0];
		boolean add = false;
		while (i[0] < S.length()) {
			if (S.charAt(i[0]) == '0') {// 如果发现0，就跳出
				i[0]++;
				add = true;
				reStringBuilder.append('1');
				break;
			}
			i[0]++;
			list.add(makeLargestSpecial(S, i));
		}
		Collections.sort(list, Collections.reverseOrder());
		for (String string : list) {
			reStringBuilder.append(string);
		}
		System.out.println(start + " " + i[0]);
		if (add) {
			reStringBuilder.append(0);
		}
		return reStringBuilder.toString();
	}

	public String makeLargestSpecialMoni(String S) {
		StringBuilder stringBuilder = new StringBuilder(S);
		HashMap<Integer, List<Integer>> index = new HashMap<>();
		findIntervals(stringBuilder, index);
		while (!index.isEmpty()) {
			// 找到最大相邻交换
			long maxDiff = 0;
			int[] res = null;
			for (Integer start : index.keySet()) {
				for (Integer mid : index.get(start)) {
					if (index.containsKey(mid + 1)) {
						for (Integer end : index.get(mid + 1)) {
							long before = Long.parseLong(stringBuilder.substring(start, end + 1), 2);
							long after = Long.parseLong(
									stringBuilder.substring(mid + 1, end + 1) + stringBuilder.substring(start, mid + 1),
									2);
							if (after - before > maxDiff) {
								maxDiff = after - before;
								res = new int[] { start, mid, end };
							}
						}
					}
				}
			}
			if (maxDiff == 0) {
				break;
			}
			// 交换
			stringBuilder = new StringBuilder(
					stringBuilder.substring(0, res[0]) + stringBuilder.substring(res[1] + 1, res[2] + 1)
							+ stringBuilder.substring(res[0], res[1] + 1) + stringBuilder.substring(res[2] + 1));
			index = new HashMap<>();
			findIntervals(stringBuilder, index);
		}
		return stringBuilder.toString();
	}

	private void findIntervals(StringBuilder stringBuilder, HashMap<Integer, List<Integer>> index) {
		int n = stringBuilder.length();
		for (int i = 0; i < n; i++) {// 从i开始
			int oneCount = 0;
			List<Integer> list = new ArrayList<>();
			for (int j = i; j < n; j++) {
				oneCount += stringBuilder.charAt(j) - '0';
				if (oneCount << 1 < j - i + 1)// 1的个数要>=0的个数，否则不是special
				{
					break;
				}
				if (oneCount << 1 == j - i + 1) {// 1的个数=0的个数
					list.add(j);
				}
			}
			if (!list.isEmpty()) {
				index.put(i, list);
			}
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String S = "11110010010011001010111010010010";// 11110010010011001010111010010010
		System.out.println(new SpecialBinaryString().makeLargestSpecial(S));// 11011000

	}

}
